/** BAD SOLUTION 648ms
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || ! head -> next || ! head -> next -> next) return;
        
        ListNode* sec_last = head;
        while(sec_last -> next -> next) 
        {
            sec_last = sec_last -> next;
        }
        ListNode* last = sec_last -> next;
        ListNode* second = head -> next;
        head -> next = last;
        sec_last -> next = NULL;
        reorderList(second);
        last -> next = second;
        return;
    }
};

/** A LIL BETTER 100ms
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;
        vector<ListNode*> vec;
        ListNode* cur = head;
        while(cur) 
        {
            vec.push_back(cur);
            cur = cur -> next;
        }
        int size = vec.size();
        int i;
        for(i = 0; i < size / 2; i++)
        {
            cout<<"for";
            vec[i] -> next = vec[size - 1 - i];
            cout<<vec[i]->val<<" "<<vec[size - 1 - i]->val<<endl;
            vec[size - 1 - i] -> next = vec[i + 1];
            cout<<vec[size - 1 - i]->val<<" "<<vec[i + 1]->val<<endl;
        }
        vec[i] -> next = NULL; // NOT i+1, HAS ALREADY + 1 !!!
        return;
    }
};


/** A LIL BETTER 100ms
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;
        vector<ListNode*> vec;
        ListNode* cur = head;
        while(cur) 
        {
            vec.push_back(cur);
            cur = cur -> next;
        }
        int size = vec.size();
        int i;
        for(i = 0; i < size / 2; i++)
        {
            cout<<"for";
            vec[i] -> next = vec[size - 1 - i];
            cout<<vec[i]->val<<" "<<vec[size - 1 - i]->val<<endl;
            vec[size - 1 - i] -> next = vec[i + 1];
            cout<<vec[size - 1 - i]->val<<" "<<vec[i + 1]->val<<endl;
        }
        vec[i] -> next = NULL; // NOT i+1, HAS ALREADY + 1 !!!
        return;
    }
};


/** BSET SOLUTION 32ms
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head -> next) return;
        // find the middle node
        ListNode *p1 = head, *p2 = head;
        while(p2 -> next && p2 -> next -> next)
        {
            p1 = p1 -> next;
            p2 = p2 -> next -> next;
        }
        // cout<<p1 -> val;
        
        //reverse the list from middle to end
        ListNode* cur = p1 -> next;
        while(cur)
        {
            // cout<<"for";
            if(!cur -> next) break;
            ListNode* n = cur -> next;
            cur -> next = n -> next;
            n -> next = p1 -> next;
            p1 -> next = n;
            // for(ListNode* p = head; p; p = p -> next)
            //     cout<<p->val<<endl;
            // cout<<endl;
        }
        
        //reset
        cur = p1 -> next;
        p1 -> next = NULL;
        ListNode* prev = head;
        while(cur)
        {
            ListNode* n_cur = cur, *n_prev = prev;
            cur = cur -> next;
            prev = prev -> next;
            n_prev -> next = n_cur;
            n_cur -> next = prev;
        }
    }
};
